///
/// \file vtblmap4.hpp
///
/// This file defines class vtblmap<N,T> used for fast mapping of N vtbl
/// pointers to type T.
///
/// \author Yuriy Solodkyy <yuriy.solodkyy@gmail.com>
///
/// This file is a part of Mach7 library (http://parasol.tamu.edu/mach7/).
/// Copyright (C) 2011-2012 Texas A&M University.
/// All rights reserved.
///

#pragma once

// --------------------[ Collisions Management ]--------------------
// Definition: Collision is condition in which cache cell for a
//             given vtbl is occupied by a different vtbl.
// Rules:
// - We only try to rearrange cache when actual collision happens
// - There is no point in rearranging if table.size() hasn't changed
// - Counting conflicts without changes in table size may decrease 
//   the counter to overflow in repetitive scenario.
// - There is always M such that growing cache to size 2^M will have
//   zero collisions. Such M is often too large to justify growth.
// - We only try log sizes N and N+1, where N = log2(|table|)
// - We do not know apriory if the set of all vtbls that will come 
//   through this vtbl_map can have 0 collisions for log size N, N+1
// - Cache arrangement with no conflicts can be a good indicator that
//   such arrangement will still be possible after adding one more vtbl.
// - Cache arrangement with conflicts will have them with more vtbls 
//   added unless the cache size got increased.
// - In most cases we'd want at least one rearrangement to happen as
//   default value for irrelevant bits is usually irrelevant for a
//   given vtbl_map and has to be recomputed.
// - We also have to avoid rearranging after every vtbl added as
//   for some especially large tables conflicts with log sizes N and
//   N+1 are unavoidable.
// - Once we found offset/size combination that renders no conflicts
//   there is no point in computing entropy further.
// - Addition of extra vtbl can make probability of conflict smaller
//   since total number of vtbls increased and we divide by it.
// - Addition of extra vtbl can make probability of conflict larger
//   when that vtbl conflicts with some that was not in conflict before.
//------------------------------------------------------------------------------

#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdarg>
#include "ptrtools.hpp"  // Helper functions to work with pointers
#include "config.hpp"    // Various compiler/platform dependent macros

#if XTL_DUMP_PERFORMANCE
// For print out purposes only
#include <array>
#include <bitset>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#endif

#define XTL_HASH_VTBL_ARRAY 1
#define XTL_VTBL_HASHING(...)     UCL_PP_IF(UCL_PP_NOT(XTL_HASH_VTBL_ARRAY), UCL_PP_EMPTY(), UCL_PP_EXPAND(__VA_ARGS__))

#include <iomanip>
#include <iostream>
struct my_if_tracer
{
    my_if_tracer(const char* s, const char* f, int l) : count_yes(0), count_no(0), text(s), file(f), line(l) {}
   ~my_if_tracer()
    {
        std::clog << file << '(' << line << ')' 
                  << (count_yes > count_no ? "   LIKELY " : " UNlikely ") 
                  << " Yes: "        << std::setw(10) << count_yes
                  << " No:  "        << std::setw(10) << count_no
                  << " Total: "      << std::setw(10) << (count_yes+count_no)
                  << " Percentage: " << std::setw(6)  << std::fixed << std::setprecision(2) << 100*double(std::max(count_yes,count_no))/(count_yes+count_no) << '%' 
                  << " Condition: "  << text
                  << std::endl;
    }

    void record(bool c)
    {
        if (c)
            count_yes++;
        else
            count_no++;
    }

    size_t count_yes;
    size_t count_no;
    const char* text;
    const char* file;
    int         line;
};

template <int line, typename T/*=void*/>
static bool my_if_trace(bool c, const char* text, const char* file)
{
    static my_if_tracer my(text,file,line);
    my.record(c);
    return c;
}

//#define XTL_TRACE_IF(c) if (my_if_trace<__LINE__>(c,#c,__FILE__))
#define XTL_TRACE_IF if 

namespace mch ///< Mach7 library namespace
{

//------------------------------------------------------------------------------

/// Type capable of representing bit offsets and bit counts in intptr_t
//typedef unsigned char  bit_offset_t;
typedef size_t  bit_offset_t;

/// The smallest integral type capable of representing the number N of different 
/// vtbl pointers in the program. Roughly N should be equal to some constant c
/// multiplied by the number of different classes polymorphic classes in the 
/// program. Constant c accounts for potential multiple inheritance.
typedef unsigned short vtbl_count_t;
//typedef size_t vtbl_count_t;

//------------------------------------------------------------------------------

const bit_offset_t min_log_size      = XTL_MIN_LOG_SIZE; ///< Log of the smallest cache size to start from
const bit_offset_t max_log_size      = XTL_MAX_LOG_SIZE; ///< Log of the largest cache size to try
const bit_offset_t max_log_inc       = XTL_MAX_LOG_INC;  ///< Log of the maximum allowed increased from the minimum requred log size (1 means twice from the min required size)
//const vtbl_count_t min_expected_size = 1 << min_log_size;
const bit_offset_t irrelevant_bits   = XTL_IRRELEVANT_VTBL_BITS;
const int initial_collisions_before_update = 1;
const int renewed_collisions_before_update = 16;

//------------------------------------------------------------------------------

#if XTL_DUMP_PERFORMANCE
template <typename T>
size_t last_non_zero_count(const T arr[/*n*/], size_t n, size_t m) // arr[i] <= m
{
    size_t result = 0;

    for (size_t i = 0; i <= m; ++i)
        if (std::count(arr,arr+n,i) > 0) 
            result = i;

    return result; // [0..m]
}

//------------------------------------------------------------------------------

template <typename T, size_t N>
inline const T (&to_array(const std::array<T,N>& arr))[N]
{
    return *reinterpret_cast<const T (*)[N]>(&arr[0]);
}
#endif

//------------------------------------------------------------------------------

template <typename T, size_t N>
inline T get_hash(const T (&a)[N])
{
    T result = a[0];
    for (size_t i = 1; i < N; ++i) result ^= a[i];
    return result;
}

//------------------------------------------------------------------------------

template <typename T, size_t N>
inline bool array_equal(const T (&a)[N], const T (&b)[N])
{
    // OVERALL: Random: 312% slower V= 67 M=276
    for (size_t i = 0; i < N; ++i)
        // OVERALL: Random: 297% slower V= 66 M=264 - XTL_LIKELY
        // OVERALL: Random: 306% slower V= 67 M=273 - XTL_UNLIKELY
        if (XTL_LIKELY(a[i] != b[i])) 
            return false;
    return true;

    // OVERALL: Random: 484% slower V= 67 M=393
    //T result = 0;
    //for (size_t i = 0; i < N; ++i)
    //    result |= a[i] ^ b[i];
    //return result == 0;

    // OVERALL: Random:1830% slower V= 71 M=1380
    //return memcmp(a,b,sizeof(a)) == 0;

    // OVERALL: Random:1818% slower V= 71 M=1364
    // return std::equal(&a[0],&a[N],&b[0]);
}

//------------------------------------------------------------------------------

template <typename T>
inline bool array_equal(const T (&a)[1], const T (&b)[1])
{
    return a[0] == b[0];
}

//------------------------------------------------------------------------------

template <typename T, size_t N>
inline void array_copy(const T (&src)[N], T (&tgt)[N])
{
    for (size_t i = 0; i < N; ++i) tgt[i] = src[i];
}

//------------------------------------------------------------------------------

template <size_t N, typename T>
class vtbl_map // For now we only rely on specializations of this class for speed
{
private:

    /// A helper data structure that is swapped during updates to 
    /// cache parameters k and l.
    struct cache_descriptor
    {
        /// Type of the stored values, which is a pair of vtbl-pointer and T value.
        struct stored_type
        {
            stored_type() : XTL_VTBL_HASHING(hash(0),) vtbl(), value() {}

            XTL_VTBL_HASHING(intptr_t hash;)     ///< hash of vtbl[i] for comparing vtbl for large N (> 2)
            intptr_t vtbl[N];  ///< v-table pointers of the value
            T        value;    ///< value associated with the v-table pointers vtbl[]

            /// Helper function to in-place construct stored_type inside uninitialized memory
            void construct()    { new(this) stored_type(); }
            /// Helper function to manually destroy stored_type
            void destroy()      { this->~stored_type(); }
            /// Checks whether given entry is already occupied
            bool occupied() const  { return vtbl[0] != 0; }
            /// Checks whether given entry is vacant
            bool vacant()   const  { return !occupied(); }
            /// Checks whether passed set of vtbl pointers matches ours set
            bool is_for(const intptr_t (&v)[N]) const { return array_equal(vtbl,v); }
            /// Optimized is_for when hash of v is known
            XTL_VTBL_HASHING(bool is_for(const intptr_t (&v)[N], intptr_t h) const { return h == hash && array_equal(vtbl,v); })
            /// Copies passed set of vtbl pointers into ours
            stored_type& operator=(const intptr_t (&v)[N]) { array_copy(v,vtbl); XTL_VTBL_HASHING(hash = get_hash(vtbl);) return *this; }
        };

        /// Cache mask to access entries. Always cache_size-1 since cache_size is a power of 2
        /// \note We currently rely in constructors on this member be first in 
        ///       declaration order so that it is initialized first!
        const size_t cache_mask;
        
        /// Optimal shift computed based on the vtbl pointers already in the map.
        /// Most of the time this value would be equal to #irrelevant_bits, but not
        /// necessarily always. In case of collisions, optimal_shift will have
        /// a value of a shift that maximizes entropy of caching vtbl pointers (which 
        /// effectively also minimizes probability of not finding something in cache)
        /*const*/ bit_offset_t optimal_shift[N];

        /// Total number of vtbl-pointers in the cache
        size_t used;

        /// Variable-sized array with actual pointers to stored_type
        stored_type* cache[XTL_VARIABLE_SIZE_ARRAY];

        #if defined(DBG_NEW)
            #undef new
        #endif

        void* operator new(size_t s, size_t log_size)
        {
            // FIX: Ensure proper alignment requirements
            return ::new char[s + ((1<<log_size)-XTL_VARIABLE_SIZE_ARRAY)*sizeof(stored_type*)];
        }

        #if defined(DBG_NEW)
            #define new DBG_NEW
        #endif

        /// We need to declare this placement delete operator since we overload new.
        void operator delete(void* p, size_t) { ::delete(static_cast<char*>(p)); } // We cast to char* to avoid warning on deleting void*, which is undefined

        /// We also provide non-placement delete operator since it doesn't really depend on extra arguments.
        void operator delete(void* p)         { ::delete(static_cast<char*>(p)); } // We cast to char* to avoid warning on deleting void*, which is undefined

        /// Creates new cache_descriptor based on parameters k and l of the hashing function
        cache_descriptor(
            const size_t       log_size,               ///< Parameter k of the cache - the log of the size of the cache
            const bit_offset_t shift = irrelevant_bits ///< Parameter l of the cache - number of irrelevant bits on the right to remove
        ) :
            cache_mask( (1<<log_size) - 1 ),
            //optimal_shift(shift),
            used(0)
        {
            // Initialize all optimal_shift values with the same value
            std::fill(&optimal_shift[0],&optimal_shift[N],shift);

            // Allocate all cache entries in one chunk for better cache performance.
            // Only allocate the difference from need and already present in old ones
            stored_type* cache_entries = new stored_type[1<<log_size];

            // Initialize pointers from cache to newly allocated cache entries
            for (size_t i = 0; i <= cache_mask; ++i)
                cache[i] = &cache_entries[i];
        }

        /// Creates new cache_descriptor based on parameters k and l of the 
        /// hashing function as well as a reference to the cache_descriptor it
        /// is going to replace.
        cache_descriptor(
            const size_t       log_size, ///< Parameter k of the cache - the log of the size of the cache                
            const bit_offset_t shifts[N],///< Parameter l of the cache - number of irrelevant bits on the right to remove
        #if defined(XTL_NO_RVALREF)
            cache_descriptor&  old       ///< cache_descriptor we will supposedly replace
        #else
            cache_descriptor&& old       ///< cache_descriptor we will supposedly replace
        #endif
        ) :
            cache_mask( (1<<log_size) - 1 ),
            //optimal_shift(shifts),
            used(old.used)
        {
            XTL_ASSERT(cache_mask >= old.cache_mask); // Since we are going to inherit all its existing elements

            std::copy(&shifts[0],&shifts[N],&optimal_shift[0]); // Initialize optimal shifts

            size_t i = 0;

            // Initialize first cache pointers to cache entries from old cache
            for (; i <= old.cache_mask; ++i)
            {
                cache[i] = 0;
                std::swap(cache[i],old.cache[i]);
            }

            if (cache_mask - old.cache_mask)
            {
                // Allocate all cache entries in one chunk for better cache performance.
                // Only allocate the difference from need and already present in old ones
                stored_type* cache_entries = new stored_type[cache_mask - old.cache_mask];

                // Initialize remaining pointers from cache to newly allocated cache entries
                for (size_t j = 0; i <= cache_mask; ++i, ++j)
                    cache[i] = &cache_entries[j];
            }

            // Bring elements to their positions in cache
            // With this:    OVERALL: Random: 136% slower V= 66 M=157
            // Without this: OVERALL: Random: 290% slower V= 67 M=262
            put_entries_in_right_place(); // Re-establish invariant
        }

        /// Deallocates memory used for elements.
        ~cache_descriptor()
        {
            // The elements will be pointing into separate arrays, we want to
            // find all the beginnings of arrays to deallocate them
            std::sort(&cache[0], &cache[cache_mask+1]);

            for (size_t i = 0; i <= cache_mask;)
            {
                if (cache[i]) // We check because subsequent descriptor could have moved out entries from this one
                {
                    size_t j = i+1;
                    for (; j <= cache_mask && intptr_t(cache[j])-intptr_t(cache[j-1]) == sizeof(stored_type); ++j);
                    delete[] cache[i];
                    i = j;
                }
                else
                    ++i;
            }
        }

        cache_descriptor& operator=(const cache_descriptor&); ///< No assignment

        bool is_full() const { return used > cache_mask; } ///< Checks whether cache is full
        size_t  size() const { return cache_mask+1; }      ///< Number of entries in cache

        size_t memory_used() const 
        {
            return sizeof(cache_descriptor)                                   // Descriptor itself
                + (cache_mask+1-XTL_VARIABLE_SIZE_ARRAY)*sizeof(stored_type*) // Pointers in cache
                + (cache_mask+1)*sizeof(stored_type);                         // Actual cached values pointers in cache point to
        }

        /// Global function computing cache index for a given vtbl pointers, offsets and cache mask
        static inline size_t cache_index(const intptr_t vtbl[N], const bit_offset_t shifts[N], size_t cache_mask)
        {
            intptr_t vtbl_shifted[N];

            for (size_t i = 0; i < N; ++i)
                vtbl_shifted[i] = vtbl[i] >> shifts[i];

            return interleave(vtbl_shifted) & cache_mask;
        }

        /// Computes cache index for current optimal offsets and cache mask.
        size_t cache_index(const intptr_t vtbl[N]) const { return cache_index(vtbl,optimal_shift,cache_mask); }

        /// Re-establishes invariant that vtbls can only be in the cache 
        /// entry that correspond to their cache index, unless that entry
        /// is already taken.
        void put_entries_in_right_place()
        {
            for (size_t i = 0; i <= cache_mask; ++i)
            {
                size_t k = ~0; // Keeps cache index of the previous swap.

                while (cache[i]->occupied()) // There is a valid tuple of vtbl pointers in the entry
                {
                    XTL_ASSERT(cache[i]->vtbl[N-1]);        // Either all 0 or all non 0
                    size_t j = cache_index(cache[i]->vtbl); // Index of location where it should be

                    if (j != k && j != i) // where it should be is not where previous one was swapped to and not here
                    {
                        std::swap(cache[i],cache[j]); // swap current to where it should be
                        k = j;                        // remember where we swapped it to
                    }
                    else
                        break;
                }
            }
        }

        /// Main function that will be used to get a reference to the stored element. 
        inline stored_type* get(const intptr_t (&vtbl)[N]) noexcept
        {
            size_t j = cache_index(vtbl);
            return get(vtbl,j);
        }
        /// Optimization for when the cache index has already been computed
        inline stored_type* get(const intptr_t (&vtbl)[N], size_t j) noexcept
        {
            XTL_ASSERT(j == cache_index(vtbl)); // j must be index of location where vtbl should be
            stored_type*& ce = cache[j]; // Location where it should be

            XTL_ASSERT(ce);   // Since we pre-allocate all entries

            XTL_TRACE_IF(XTL_UNLIKELY(ce->is_for(vtbl))) // FIX: Maybe we should eliminate it at all since we check it in vtbl_map::get!
                return ce;

            // When the entry is occupied, our combination can be elsewhere in 
            // the cache due to collisions, however when the entry is not 
            // occupied, we do not have to search whether it is in the cache as
            // constructor establishes invariant that entries can only be in
            // their place.
            XTL_TRACE_IF(XTL_LIKELY(ce->occupied()))
            {
                // Precompute hash of the vtbl array for faster comparisons.
                XTL_VTBL_HASHING(const intptr_t vtbl_hash = get_hash(vtbl);)

                // See if (vtbl0,...,vtblN) is elsewhere in the cache
                // Start from the next location after j till end
                for (size_t i = j+1; i <= cache_mask; ++i)
                    XTL_TRACE_IF(XTL_UNLIKELY(cache[i]->is_for(vtbl XTL_VTBL_HASHING(,vtbl_hash)))) // if so ...
                    {
                        std::swap(ce,cache[i]); // swap it with the right position
                        return ce;
                    }
                // If not found, continue from the beginning until j
                for (size_t i = 0; i < j; ++i)
                    XTL_TRACE_IF(XTL_UNLIKELY(cache[i]->is_for(vtbl XTL_VTBL_HASHING(,vtbl_hash)))) // if so ...
                    {
                        std::swap(ce,cache[i]); // swap it with the right position
                        return ce;
                    }
            }

            // (vtbl0,...,vtblN) is not in the cache
            XTL_TRACE_IF(XTL_LIKELY(used <= cache_mask)) // there are empty slots in cache
            {
                // Start from j (since it can be empty) till end
                for (size_t i = j; i <= cache_mask; ++i)
                    XTL_TRACE_IF(XTL_UNLIKELY(cache[i]->vacant())) // find the first empty slot
                    {
                        XTL_ASSERT(cache[i]->vtbl[N-1] == 0); // Either all 0 or all non 0
                        *cache[i] = vtbl; //array_copy(vtbl,cache[i]->vtbl);
                        ++used;
                        std::swap(ce,cache[i]); // swap it with the right position
                        return ce;
                    }
                // If not found, continue from the beginning until j
                for (size_t i = 0; i < j; ++i)
                    XTL_TRACE_IF(XTL_UNLIKELY(cache[i]->vacant())) // find the first empty slot
                    {
                        XTL_ASSERT(cache[i]->vtbl[N-1] == 0); // Either all 0 or all non 0
                        *cache[i] = vtbl; //array_copy(vtbl,cache[i]->vtbl);
                        ++used;
                        std::swap(ce,cache[i]); // swap it with the right position
                        return ce;
                    }
            }

            // There are no empty slots, we return nullptr to indicate this
            return 0;
        }
    };

public:
    
#if XTL_DUMP_PERFORMANCE
    #if defined(DBG_NEW)
        #undef new
    #endif
    vtbl_map(const char* fl, size_t ln, const char* fn, const vtbl_count_t& num_clauses) : 
        descriptor(new(min_log_size) cache_descriptor(min_log_size)),
        case_clauses(num_clauses),
        last_table_size(0),
        collisions_before_update(initial_collisions_before_update),
        file(fl), 
        line(ln),
        func(fn),
        updates(0), 
        hits(0),
        misses(0),
        collisions(0)
    {}
    #if defined(DBG_NEW)
        #define new DBG_NEW
    #endif
#endif

    #if defined(DBG_NEW)
        #undef new
    #endif
    vtbl_map(const vtbl_count_t& num_clauses) : 
        descriptor(new(min_log_size) cache_descriptor(min_log_size)),
        case_clauses(num_clauses),
        last_table_size(0),
        collisions_before_update(initial_collisions_before_update)
        XTL_DUMP_PERFORMANCE_ONLY(,file("unspecified"), line(0), func("unspecified"), updates(0), hits(0), misses(0), collisions(0))
    {}
    #if defined(DBG_NEW)
        #define new DBG_NEW
    #endif

   ~vtbl_map()
    {
        XTL_DUMP_PERFORMANCE_ONLY(std::clog << *this << std::endl);
        delete descriptor;
    }

    size_t memory_used() const 
    {
        XTL_ASSERT(descriptor);
        return sizeof(vtbl_map) + descriptor->memory_used();
    }

    /// This is the main function to get the value of type T associated with
    /// the (vtbl0,...,vtblN) of given pointers.
    ///
    /// \note The function returns the value "by reference" to indicate that you 
    ///       may take address or change the value of the cell!
    inline T& get(intptr_t vtbl0, ...) noexcept
    {
        XTL_ASSERT(descriptor); // Allocated in constructor, deallocated in destructor

        intptr_t vtbl[N] = {vtbl0};

        va_list vl;
        va_start(vl,vtbl0);

        for (size_t i = 1; i < N; i++)
        {
            intptr_t vtbl_i = va_arg(vl,intptr_t);
            XTL_ASSERT(vtbl_i); // Must be a valid vtbl pointer
            vtbl[i] = vtbl_i;
        }

        va_end(vl);
        return get(vtbl);
    }

    inline T& get(const intptr_t (&vtbl)[N]) noexcept
    {
        size_t j = descriptor->cache_index(vtbl);  // Index of location where it should be
        typename cache_descriptor::stored_type*& ce = descriptor->cache[j]; // Location where it should be

        XTL_ASSERT(ce);   // Since we pre-allocate all entries

        XTL_TRACE_IF(XTL_LIKELY(ce->is_for(vtbl)))
        {
            XTL_DUMP_PERFORMANCE_ONLY(++hits);
            return ce->value;
        }
        else
        {
            XTL_DUMP_PERFORMANCE_ONLY(++misses);
            XTL_DUMP_PERFORMANCE_ONLY(if (ce->occupied()) ++collisions);

            XTL_TRACE_IF(XTL_UNLIKELY(
                descriptor->is_full()                     // No entries left for possibly new vtbl in the cache
                || (ce->occupied()                        // Collision - the entry for vtbl is already occupied
                && --collisions_before_update <= 0        // We had sufficiently many collisions to justify call
                && descriptor->used != last_table_size))) // There was at least one vtbl added since last update
                return update(vtbl);                      // try to rearrange cache

            // Try to find entry with our vtbl and swap it with where it is expected to be
            descriptor->get(vtbl,j); // This will bring correct pointer into ce
            XTL_ASSERT(ce->is_for(vtbl));
            return ce->value;
        }
    }

    /// A function that gets called when the cache is either too inefficient or full.
    T& update(const intptr_t (&vtbl)[N]);

#if XTL_DUMP_PERFORMANCE
    std::ostream& operator>>(std::ostream& os) const;
    friend std::ostream& operator<<(std::ostream& os, const vtbl_map& m) { return m >> os; }
#endif

private:

    /// Cached mappings of vtbl to some indecies
    cache_descriptor* descriptor;

    /// A reference to a global variable that will be initialized with the number of case clauses of a given match statement
    const vtbl_count_t& case_clauses;

    /// Memoized table.size() during last cache rearranging
    size_t last_table_size;

    /// Number of colisions that we will still tolerate before next update
    int collisions_before_update;

#if XTL_DUMP_PERFORMANCE
    const char* file;      ///< File in which this vtblmap_of is instantiated
    size_t      line;      ///< Line in the file where it is instantiated
    const char* func;      ///< Function in which this vtblmap_of is instantiated
    size_t      updates;   ///< Amount of reconfigurations performed at run time
    size_t      hits;      ///< The number of cache hits
    size_t      misses;    ///< The number of cache misses
    size_t      collisions;///< Out of all the misses, how many were actual collisions
#endif

};

//------------------------------------------------------------------------------

template <size_t N, typename T>
T& vtbl_map<N,T>::update(const intptr_t (&vtbl)[N])
{
    XTL_ASSERT(descriptor); // Allocated in constructor, deallocated in destructor
    XTL_ASSERT(last_table_size < descriptor->used || descriptor->is_full()); // We will only call this if size changed

    // FIX: vtbl might already exist in old descriptor and if it happens to be the first one, it won't be taken into consideration
    intptr_t prev[N];
    intptr_t diff[N] = {};

    array_copy(vtbl,prev);

    // Compute bits in which existing vtbl, including the newly added one, differ
    for (size_t i = 0; i <= descriptor->cache_mask; ++i)
    {
        typename cache_descriptor::stored_type* const st = descriptor->cache[i];

        XTL_ASSERT(st);

        for (size_t s = 0; s < N; s++)
            if (intptr_t vtbl = st->vtbl[s])
            {
                diff[s] |= prev[s] ^ vtbl;
                prev[s] = vtbl;
            }
    }

//#if XTL_DUMP_PERFORMANCE
//        std::clog << "\nVtbl:New" << std::bitset<8*sizeof(intptr_t)>((unsigned long long)vtbl) << " -> " << ((vtbl >> optimal_shift) & cache_mask) << '\t' << vtbl_typeid(vtbl).name() << std::endl;
//        *this >> std::clog;       
//#endif

    XTL_DUMP_PERFORMANCE_ONLY(++updates); // Record update
    collisions_before_update = renewed_collisions_before_update;      // Reset collisions counter

    bit_offset_t k  = bit_offset_t(req_bits(descriptor->cache_mask)); // current log_size
    bit_offset_t n  = bit_offset_t(req_bits(std::max<size_t>(descriptor->used,case_clauses))); // needed  log_size. NOTE: case_clauses will be initialized by now
    bit_offset_t m[N];    // highest bit in which vtbls differ
    bit_offset_t z[N];    // lowest bits in which vtbls do not differ
    bit_offset_t l1 = std::min(max_log_size,std::max(k,n));                          // lower bound for log_size iteration
    bit_offset_t l2 = std::min(max_log_size,std::max(k,bit_offset_t(n+max_log_inc)));// upper bound for log_size iteration
    bit_offset_t no = l1; // current estimate of the best log_size
    bit_offset_t zo[N];   // current estimate of the best offset

    for (size_t i = 0; i < N; ++i)
    {
        m[i] = bit_offset_t(req_bits(diff[i])); // highest bit in which vtbls differ
        z[i] = bit_offset_t(trailing_zeros(static_cast<unsigned int>(diff[i]))); // lowest bits in which vtbls do not differ
        zo[i] = z[i];                           // current estimate of the best offset
    }

    // FIX: Ensure we do not run out of stack, since in new implementation we don't have hash tables anymore
    // We do this to not resort to vectors and heap and keep counting on stack
    const size_t cache_histogram_size = 1 + ((1<<l2) - 1)/XTL_BIT_SIZE(intptr_t);
    XTL_VLA(cache_histogram, intptr_t, cache_histogram_size, 1 + ((1<<max_log_size) - 1)/XTL_BIT_SIZE(intptr_t)); // intptr_t cache_histogram[cache_histogram_size];

    size_t max_cache_entries = 0;

    // Iterate over allowed log sizes
    for (bit_offset_t i = l1; i <= l2; ++i)
    {
        const size_t   cache_size = 1<<i;
        const intptr_t cache_mask = cache_size-1;

        bit_offset_t j[N];

        array_copy(z,j);

        // Iterate over possible offsets
        for (size_t q = 0; q < N;)
        {
            std::memset(cache_histogram,0,cache_histogram_size*sizeof(intptr_t)); // Reset bit histogram to zeros
            XTL_BIT_SET(cache_histogram, cache_descriptor::cache_index(vtbl,j,cache_mask)); // Mark the entry for new vtbl

            // Iterate over vtbl in old cache and see where they are mapped with log size i and offset j
            for (size_t c = 0; c <= descriptor->cache_mask; ++c)
            {
                typename cache_descriptor::stored_type* const st = descriptor->cache[c];

                XTL_ASSERT(st);

                if (st->occupied())
                    XTL_BIT_SET(cache_histogram, cache_descriptor::cache_index(st->vtbl,j,cache_mask)); // Mark the entry for each vtbl
            }

            size_t entries = 0;

            // Count the number of used entries
            for (size_t h = 0; h < cache_histogram_size; ++h)
                entries += bits_set(cache_histogram[h]);

            // Update best estimates
            if (entries > max_cache_entries)
            {
                max_cache_entries = entries;
                no = i;
                array_copy(j,zo);
            }

            if (entries == descriptor->used+1)
            {
                // We found size and offset without conflicts, exit both loops
                i = l2+1; // to exit both for loops
                //collisions_before_update = initial_collisions_before_update; // since it is likely that adding another vtbl may still render no conflicts
                break;
            }

            // Update current offsets
            while (j[q]==m[q] && q < N)
            {
                j[q] = z[q];
                ++q;
            }

            if (q < N)
                ++j[q];
        }
    }

    if (no < k)
        no = k; // We never shrink, while we preallocate based on number of case clauses or the minimum

    if (no != k || !array_equal(descriptor->optimal_shift,zo))
    {
        cache_descriptor* old = descriptor;
        #if defined(DBG_NEW)
            #undef new
        #endif
        #if defined(XTL_NO_RVALREF)
            descriptor = new(no) cache_descriptor(no,zo,*old);
        #else
            descriptor = new(no) cache_descriptor(no,zo,std::move(*old));
        #endif
        #if defined(DBG_NEW)
            #define new DBG_NEW
        #endif
        delete old;
    }

//#if XTL_DUMP_PERFORMANCE
//        std::clog << "After" << std::endl;
//        *this >> std::clog;       
//#endif
    typename cache_descriptor::stored_type* res = descriptor->get(vtbl);
    XTL_ASSERT(res && res->is_for(vtbl)); // We have ensured enough space, so no need to check this explicitly
    last_table_size = descriptor->used;   // Update memoized value
    return res->value;
}

//------------------------------------------------------------------------------

#if XTL_DUMP_PERFORMANCE
template <size_t N, typename T>
std::ostream& vtbl_map<N,T>::operator>>(std::ostream& os) const
{
    std::ios::fmtflags fmt = os.flags(); // store flags

    os << file << '[' << line << ']' << ' ' << func << std::endl;

    size_t vtbl_count = descriptor->used;
    size_t log_size   = req_bits(descriptor->cache_mask);
    size_t cache_size = (1<<log_size);

    // We do this to not resort to vectors and heap and keep counting on stack
    XTL_VLAZ(cache_histogram, vtbl_count_t, cache_size, 1<<max_log_size); // vtbl_count_t cache_histogram[cache_size];

    std::vector<std::array<intptr_t,N>> vtbls(vtbl_count);
    typename std::vector<std::array<intptr_t,N>>::iterator q = vtbls.begin();

    intptr_t prev[N] = {};
    intptr_t diff[N] = {};

    // Compute bits in which existing vtbl, including the newly added one, differ
    for (size_t i = 0; i <= descriptor->cache_mask; ++i)
    {
        typename cache_descriptor::stored_type* const st = descriptor->cache[i];

        XTL_ASSERT(st);

        if (st->occupied())
        {
            std::array<intptr_t,N> a;

            for (size_t s = 0; s < N; s++)
            {
                intptr_t vtbl = a[s] = st->vtbl[s];

                XTL_ASSERT(vtbl); 

                if (prev[s]) diff[s] |= prev[s] ^ vtbl; // Update diff with information about which bits in all vtbls differ
                prev[s] = vtbl;
            }

            cache_histogram[cache_descriptor::cache_index(to_array(a),descriptor->optimal_shift,descriptor->cache_mask)]++;
            XTL_ASSERT(size_t(q-vtbls.begin()) < vtbl_count); // Since we preallocated only that much
            *q++ = a;
        }
    }

    // Sort vtables to output them in address order
    std::sort(vtbls.begin(),vtbls.end());
    std::fill(&prev[0],&prev[N],0);

    for (q = vtbls.begin(); q != vtbls.end(); ++q)
    {
        const std::array<intptr_t,N>& a = *q;
        os << "Vtbl:   ";

        for (size_t s = 0; s < N; s++)
        {
            intptr_t vtbl = a[s];
            os << (s ? " | " : "") << std::bitset<8*sizeof(intptr_t)>((unsigned long long)vtbl); // Show binary value of vtbl pointer
        }

        os << " -> " << std::setw(3) << descriptor->cache_index(to_array(a))    // Show cache index it is mapped to
           << ' ';
            
        std::copy(a.begin(),a.end(),&prev[0]);

        if (cache_histogram[descriptor->cache_index(to_array(a))] > 1)
            os << '[' << cache_histogram[descriptor->cache_index(to_array(a))] << ']'; // Show have many vtbl falls into the same cache index
        else
            os << "   ";

        os << '\t';

        for (size_t s = 0; s < N; s++)
        {
            intptr_t vtbl = a[s];
            os << (s ? "," : "") << vtbl_typeid(vtbl).name(); // Show name of the class of this vtbl
        }

        os << std::endl; // Show name of the class of this vtbl
    }

    os.flags(fmt);

    std::string outstr;

    for (size_t s = 0; s < N; s++)
    {
        // FIX: G++ crashes when we use std::stringstream here, so we have to workaround it manually
        std::string str(8*sizeof(prev[0]),'0');

        for (size_t j = 1, i = 8*sizeof(prev[0]); i; --i, j<<=1)
            if (diff[s] & j)
                str[i-1] = j & (((1 << (log_size+N-1-s)/N) - 1) << descriptor->optimal_shift[s]) ? 'x' : 'X'; // Indicate bit positions used for computing the hash after interleaving
            else
            if (prev[s] & j)
                str[i-1] = '1';

        outstr += (s ? " | " : "") + str;
    }

    os  << "VTBLS:  "     << outstr       << std::endl
        << " clauses="    << std::setw(4) << case_clauses // Number of case clauses in the match statement
        << " total="      << std::setw(5) << vtbl_count   // Total number of vtbl pointers seen
        << " log_size="   << std::setw(2) << log_size     // log2 size required
        << " updates="    << std::setw(2) << updates      // how many updates have been performed on the cache
        << " hits="       << std::setw(8) << hits         // how many hits have we had
        << " misses="     << std::setw(8) << misses       // how many misses have we had
        << " collisions=" << std::setw(8) << collisions   // how many misses were actual collisions
        << " memory="     << std::setw(8) << memory_used()// number of bytes used
        << " Stmt: "      << file << '[' << line << ']' << ' ' << func
        << ";\n";
    os.flags(fmt);
#if 0
    bit_offset_t k  = req_bits(cache_mask);     // current log_size
    bit_offset_t n  = req_bits(vtbl_count-1);   // needed  log_size
    bit_offset_t m  = req_bits(diff);           // highest bit in which vtbls differ
    bit_offset_t z  = trailing_zeros(static_cast<unsigned int>(diff)); // number of lowest bits in which vtbls do not differ
    bit_offset_t l1 = std::min(max_log_size,std::min(k,n));
    bit_offset_t l2 = std::min(max_log_size,std::max(k,bit_offset_t(n+max_log_inc)));

    for (bit_offset_t i = l1; i <= l2; ++i)
    {
        for (bit_offset_t j = z; j <= m-i; ++j)
        {
            double e, p;
            size_t t = get_stats_for(i,j,e,p);
            os  << "\tlog_size=" << std::setw(2) << int(i) 
                << " shift="     << std::setw(2) << int(j) 
                << " Entropy="   << std::setw(10)<< std::fixed << std::setprecision(7) << e 
                << " Conflict="  << std::setw(9) << std::fixed << std::setprecision(7) << p << (t == vtbl_count ? " \t*" : "") 
                << std::endl;
        }
    }
    os.flags(fmt);
#endif

    size_t d0 = 0, d1 = 0;
    double cache_conflict = 0.0;

    // Compute cache's probability of conflict
    for (size_t j = 0; j < cache_size; ++j)
    {
        size_t c = cache_histogram[j];
        if (c == 0) ++d0;
        if (c == 1) ++d1;
        if (c >  1) cache_conflict += double(c-1)/vtbl_count;
    }
    
    // Show cache's parameters
    os  << "\nCache:"
        << " buckets="     << std::setw(4) << cache_size
        << " load_factor=" << std::setw(4) << std::fixed << std::setprecision(2) << double(cache_size-d0)/cache_size
        << " perfect="     << std::setw(3) << (vtbl_count ? d1*100/vtbl_count : 0) << '%'
        << " conflict="    << std::setw(9) << std::fixed << std::setprecision(7) << cache_conflict // Probability of conflict in cache
        << " Stmt: "       << file << '[' << line << ']' << ' ' << func
        << "; ";

    size_t cache_last_non_zero_count = last_non_zero_count(cache_histogram,cache_size,vtbl_count);

    // Print cache histogram
    for (size_t i = 0; i <= cache_last_non_zero_count; ++i)
    {
        size_t d = std::count(cache_histogram,cache_histogram+cache_size,i);

        if (!i) os << std::setw(3) << d*100/cache_size << "% unused " << '[' << line << ']';
        os << std::setw(2) << i << "->" << d << "; ";
    }

    os.flags(fmt);

    // Print map of cache entries occupation
    for (size_t j = 0; j < cache_size; ++j)
    {
        const size_t entries_per_row = 64;

        if (j % entries_per_row == 0)
            os << std::endl << std::setw(4) << std::hex << j << ": ";

        size_t n = cache_histogram[j];

        char c;

        switch (n)
        {
        case 0:  c = descriptor->cache[j]->occupied() ? '*' : '.'; break;
        case 1:  c = '1'; break;
        case 2:  c = '2'; break;
        case 3:  c = '3'; break;
        case 4:  c = '4'; break;
        case 5:  c = '5'; break;
        default: c = 'X'; break;
        }
        
        os << c;
    }

    os.flags(fmt);
    return os << std::endl;
}
#endif

//------------------------------------------------------------------------------

/// Data structure used by our Match statements to associate jump target and the 
/// required offset with the vtbl-pointer.
template <size_t N>
struct type_switch_info
{
    std::ptrdiff_t offset[N]; ///< Required this-pointer offset to the source sub-object
    std::size_t    target;    ///< Case label of the jump target of Match statement
};

//------------------------------------------------------------------------------

} // of namespace mch

// Generic M and V without vtbl array hashing are:
// N=1:  100 combinations V=50 M=53  -   5% slower
// N=2:  100 combinations V=55 M=38  -  43% faster
// N=3: 1000 combinations V=68 M=69  -   2% slower

// Generic M and V with vtbl array hashing are:
// N=1:  100 combinations V=56 M=53  -   4% faster
// N=2:  100 combinations V=52 M=36  -  42% faster
// N=3: 1000 combinations V=67 M=63  -   7% faster
// Hashing thus improves performance for N >= 3

// Specialized M and V without vtbl array hashing are:
// N=1:  100 combinations V=51 M=54  -   6% slower
// N=2:  100 combinations V=58 M=35  -  62% faster
// N=3: 1000 combinations V=63 M=70  -  10% slower

//#include "vtblmap4st-1.hpp" // Implementation of vtbl_map<1,T> partial specialization
//#include "vtblmap4st-2.hpp" // Implementation of vtbl_map<2,T> partial specialization
//#include "vtblmap4st-3.hpp" // Implementation of vtbl_map<3,T> partial specialization

//------------------------------------------------------------------------------
#undef if
